1. Field of the Invention
The present invention relates to the field of processors and, more particularly, to a technique for providing memory access ordering in a multiple processing environment.
2. Background of the Related Art
In an operation of a processor the order in which program instructions are executed is critical to the proper operation of the processor. Where earlier processors executed memory accessing operations in the order in which the instructions were executed by a program, more advanced processors have the capability of changing the order in which the accesses are made to memory, provided that the processor maintains a record of the proper order of the memory accesses. The technique of reordering memory accesses (such as read and write operations to memory) is especially desirable, since such reordering can enhance the speed of data processing. For example, if a particular access to memory is pending for a variety of reasons, the processor can continue with the next access if reordering is permitted. Otherwise, the processor must wait until the current access is completed, before proceeding with the next access. Thus, there is a significant advantage in performance if memory accesses can be performed in the order other than the order required by the program.
Accordingly, in more advanced processors, the ordering of "reads" and/or "writes" (also referred to as "loads" and "stores") from/to memory can be changed from the actual sequence provided by the execution of the program instructions. Again, the processor maintains the necessary control so that the final order of the various results of the accesses is consistent with the program instructions. This is also true, where cache memory or memories are used in conjunction with main memory storage. In that instance, the memory access ordering control is complicated by the maintaining of the location of the valid data, but the overall concept is the same.
However, when multiple processors (or devices capable of accessing memory) are utilized in which a given memory or a portion of a memory is shared by more than one processor, an added constraint is placed on the multiple processor computer system to ensure that the ordering of memory accesses from one processor is made visible to the other processors, according to the order of the program instructions, at least as to the shared memory space. That is, where each individual processor can maintain a record of reordering memory accesses it generates, the other processor(s) may not know that this reordering has occurred. Accordingly, an access to a shared memory location generated by a processor in the system must be observed by (made visible to) the other processor(s) in the same order as noted in the program, unless a mechanism is in place to permit reordering. Otherwise, there exists a possibility that the data obtained by one processor may not be the valid data as required by the program.
One mechanism for controlling accesses to a memory area shared by multiple processors is the use of a semaphore (or flag) as a "key" for obtaining entry into the shared space. In this scheme, a processor can obtain entry into the shared memory area only if it gains access to the "lock" controlling the shared memory area. Only one processor is permitted to gain control of the lock at any one time. Once a processor gains entry into the shared memory area by acquiring the lock, it must then set the semaphore so as to prevent any other processor from gaining entry into the shared space until the lock is released. Typically, a particular address location is designated as the lock and values written to this address location determine the states of the semaphore.
By utilizing the above described locking scheme, reordering of accesses is a concern when accesses are made to acquire or release the lock to the shared memory space. Each processor is generally free to reorder accesses to its non-shared memory space, since this space is not accessed by the other processor(s) and such accesses to non-shared memory space need not be made visible to the other processor(s) in the proper order. It is appreciated that other devices, such as input/output devices, may also require such access ordering control. The access ordering control is important where two accesses must be done in order. Thus, access ordering is not limited to the access of memory only.
Visibility of an access is defined for a read and a write as follows. A read to an address A by a processor P1 is considered visible from the point of view of a second processor P2, if a write to address A issued by P2 cannot change the value read by P1. Likewise, a write to an address A by processor P1 is considered visible from the point of view of a second processor P2, if a read from address A issued by the program cannot return the value of A prior to the write by P1.
The use of semaphores to control accesses to the shared memory space can provide adequate controls once a processor gains entry into the shared space. However, a problem still resides in properly ordering the accesses for acquiring and releasing the lock. Since memory accesses are needed for acquiring and releasing the lock, it is possible for a processor to reorder these accesses in reference to its other memory accesses, including memory accesses to the shared memory space. Since the lock location is shared by the other processor(s) in the system, the accesses to acquire and release the lock may not be visible to the other processors in the proper sequence relative to the accesses to the shared area of memory. Thus, some mechanism is still needed to maintain ordering for memory accesses for acquiring and releasing the lock in order to make these accesses visible.
Accordingly, the present invention provides for a technique of controlling memory access ordering in a system that has multiple memory accessing devices and in which more than one such device is permitted access to a shared location in memory. Furthermore, the technique of the present invention provides memory access ordering through instruction support, but without requiring modifications to existing load and store instructions which are used to access the memory.